package com.Oct_TwentyThree;

import java.util.ArrayList;
import java.util.List;

/**
 * 990. 等式方程的可满足性
 * 给定一个由表示变量之间关系的字符串方程组成的数组，每个字符串方程 equations[i] 的长度为 4，并采用两种不同的形式之一："a==b" 或 "a!=b"。在这里，a 和 b 是小写字母（不一定不同），表示单字母变量名。
 *
 * 只有当可以将整数分配给变量名，以便满足所有给定的方程时才返回 true，否则返回 false。 
 *
 *  
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/satisfiability-of-equality-equations
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * 2022/10/23 11:45
 */

public class Solution990 {

    public boolean equationsPossible(String[] equations) {
        init();
        List<int[]> list=new ArrayList<>();
        int n=equations.length;
        for (String equation : equations) {
            char a = equation.charAt(0);
            char b = equation.charAt(3);
            if (equation.charAt(1) == '=') {
                union(a - 'a', b - 'a');
            } else {
                list.add(new int[]{a - 'a', b - 'a'});
            }
        }
        for (int[] temp :
                list) {
            if (find(temp[0]) == find(temp[1]))
            {
                return false;
            }
        }
        return true;
    }

    int[] father;

    void init(){
        father=new int[27];
        for (int i=0;i< father.length;i++)
        {
            father[i]=i;
        }
    }

    int find(int u){
        return u==father[u]?u:(father[u]=find(father[u]));
    }

    void union(int u,int v){
        u=find(u);
        v=find(v);
        if (u==v) return;
        father[v]=u;
    }

    public static void main(String[] args) {
        Solution990 solution990=new Solution990();
        System.out.println(solution990.equationsPossible(new String[]{"a==b","b==c","a==c"}));
    }

}
